package nan.LinkedList;

public class Main2 {
    public static Node2 createList(){
        Node2 a=new Node2(1);
        Node2 b=new Node2(2);
        Node2 c=new Node2(3);
        Node2 d=new Node2(4);
        a.next=b;
        b.next=c;
        c.next=d;
        d.next=null;
        return a;
    }
    //创建一个带傀儡节点的链表
    //本质的区别在于“傀儡节点”中的值是不适用的，下面的链表长度认为是4
    public static Node2 createListWithDummy(){
        Node2 dummy=new Node2(0);
        Node2 a=new Node2(1);
        Node2 b=new Node2(2);
        Node2 c=new Node2(3);
        Node2 d=new Node2(4);
        dummy.next=a;
        a.next=b;
        b.next=c;
        c.next=d;
        d.next=null;
        return dummy;
    }

    public static void printLy(Node2 head){
        for(Node2 cur=head;cur!=null;cur=cur.next){
            System.out.println(cur.val);
        }
    }
    //尾插一个节点
    public static void insertTail(Node2 head,int val){
        if(head==null){
            return;
        }
        //先找到末尾节点
        Node2 prev=head;
        while(prev.next!=null){
            prev=prev.next;
        }
        //循环结束，cur就是最后一个节点了
        Node2 newNode=new Node2(val);
        newNode.next=prev.next;
        prev.next=newNode;
    }

    //删除一个节点.此处是按照值来删除
    public static Node2 remove( Node2 head,int val){
        if(head==null){
            return null;
        }
        if(head.val==val){
            //要删除的节点就是头结点
            head=head.next;
            return head;
        }
        //1.先找到val这个值对应的位置，并且也要找到val的前一个位置
        Node2 prev=head;
        while(prev!=null&&prev.next!=null&&prev.next.val!=val){
            prev=prev.next;
        }
        //循环结束之后，prev就指向待删除节点的前一个节点了
        if(prev==null||prev.next==null){
            return head;//没有找到值为val的
        }
        //2.真正进行删除,toDelete指向要被删除的节点
        Node2 toDelete=prev.next;
        prev.next=toDelete.next;
        return head;//返回原来的链表
    }
    //删除节点，按照位置来删除
    public static Node2 remove(Node2 head,Node2 toDelete){
        if(head==null){
            return null;
        }
        if(head==toDelete){//删除头结点
            head=head.next;
            return head;
        }
        //1.现需要找到toDelete的前一个节点，
        Node2 prev=head;
        while(prev!=null&&prev.next!=toDelete){
            prev=prev.next;
        }
        if(prev==null){
            //没找到
            return head;
        }
        //2.进行删除
        prev.next=toDelete.next;
        return head;
    }
    public static int size(Node2 head){
        int size=0;
        for(Node2 cur=head;cur!=null;cur=cur.next){
            size++;
        }
        return size;
    }
    //给定节点下标删除
    public static Node2 remove2(Node2 head,int index){
        //如果index为0，就是删除头结点
        if(index==0){
            head=head.next;
            return head;
        }
        //还是要找到待删除节点的前一个位置，index—1这个节点就是前一个位置
        Node2 prev=head;
        for(int i=0;i<index-1;i++){
           prev=prev.next;
        }
        //循环结束之后，找到了index—1
        Node2 toDelete=prev.next;
        prev.next=toDelete.next;
        return head;
    }

    //删除操作
    public static Node2 removeWithDummy(Node2 head,int val){
        Node2 prev=head;
        while(prev!=null&&prev.next!=null&&prev.next.val!=val){
            prev=prev.next;
        }
        //循环结束，要么是prev到达了链表末尾，要么是找到了val匹配的值
        if(prev==null||prev.next==null){//没有找到对应的节点
            return head;
        }
        //找到对应节点
        Node2 toDelete=prev.next;
        prev.next=toDelete.next;
        return head;
    }
    //删除最后一个
    public static Node2 removeTail(Node2 head){
        if(head==null){
            return null;
        }
        if(head.next==null){
            return null;
        }
        Node2 prev=head;
        Node2 toDelete=prev.next;
        while(prev!=null&&prev.next!=null&&prev.next.next!=null){
            prev=prev.next;
        }
        //prev.next=null;
        prev.next=toDelete.next;
        return head;
    }
    // 请将给定数组，转换成链表
    public static Node2 arrayToLinkedList(int[] array){
        //遍历数组，把每一个元素依次进行尾插
        //每次尾插，都需要知道当前链表的末尾节点，每次都要重新找，太麻烦了
        //可以直接使用一个引用，把尾节点记住。
        Node2 head=null;//head就是头结点的引用，初始情况下，链表是空的
        Node2 tail=null;
        for(int x:array){
            Node2 node2=new Node2(x);
            //把node进行尾插
            //需要判断当前链表是否为空
            if(head==null){
                head=node2;
                tail=node2;
            }else{//链表不为空的时候，不用管head了，直接操作tail
                tail.next=node2;
                tail=tail.next;
            }
        }
        return head;
    }
    public static Node2 arrayToLinkedList2(int[] array){
        //创建了一个带傀儡节点的链表；
        Node2 head=new Node2(0);
        Node2 tail=head;
        for(int x:array){
            Node2 node2=new Node2(x);
            tail.next=node2;
            tail=tail.next;
        }
        return head.next;
    }
    public static void main(String[] args) {
//        Node2 head=createList();
//
//
//
//        //把节点插入到1,2之间
//        Node2 one=head;
//        //创建一个新的节点
//        Node2 newNode=new Node2(100);
//        //先让新节点的next指向one的next
//        newNode.next=one.next;
//        //再让one的next指向新的节点
//        one.next=newNode;
//
//
//
//        //把节点插入到链表头部
//        Node2 newNode2=new Node2(20);
//        //先让新节点的next指向head
//        newNode2.next=head;
//        //head再指向新的节点
//        head=newNode2;
        //创建带傀儡节点的链表
//        Node2 head=createListWithDummy();
        //创建newNode
//        Node2 newNode=new Node2(100);
        //1.往中间插入，例如往1,2之间插入
//        Node2 prev=head.next;//prev就是指向1的位置
//        newNode.next=prev.next;
//        prev.next=newNode;
        //2.往头部插入
//        Node2 prev=head;
//        newNode.next=prev.next;
//        prev.next=newNode;
//
//
//        Node2 head2=createList();
//        insertTail(head2,100);
//        System.out.println(remove2(head2,3));

//        Node2 head3=createListWithDummy();
//        removeWithDummy(head3,1);
        int[] array={1,2,3,4,5};
        Node2 head4=arrayToLinkedList(array);
        printLy(head4);
    }
}
